import java.util.Arrays;


/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: lishuo
 * Date: 2023-01-11
 * Time: 17:15
 */
public class PriorityQueue {
    public int[] elem;
    public int usedSize;

    public PriorityQueue(){
        elem = new int[10];
    }

    public void Init(int[] array) {
        this.elem = Arrays.copyOf(array, array.length);
        this.usedSize = array.length;

    }


    /**
     * 建堆：时间复杂度：O(N)
     * @param array
     */
    public void creatHeap(int[] array) {

        for (int parent = (usedSize-1-1)/2; parent >= 0 ; parent--) {
            SshiftDown(parent,usedSize);
        }
    }

    //大根堆->向下调整：时间复杂度：O(树的高度)->O(NlogN)
    /**
     * 大根堆->向下调整算法
     * @param parent
     * @param len
     */
    private void BshiftDown(int parent, int len) {
        //有左孩子
        int child = 2 * parent + 1;//这里是+1！！！

        while (child < len) {
            //有右孩子
            if (child + 1 < len && elem[child] < elem[child + 1]) {
                child++;
            }
            //此时childe一定是左右孩子的最大值的下标
            if (elem[child] > elem[parent]) {
                int tmp = elem[parent];
                elem[parent] = elem[child];
                elem[child] = tmp;

                parent = child;
                child = 2 * parent + 1;
            } else {
                break;
            }
        }
    }


    /**
     * 小根堆->向下调整算法
     * @param parent 待调整结点
     * @param len 数组长度
     */
    private void SshiftDown(int parent, int len) {
        //有左孩子
        int child = 2 * parent + 1;//这里是+1！！！

        while (child < len) {
            //有右孩子
            if (child + 1 < len && elem[child] > elem[child + 1]) {
                child++;
            }
            //此时childe一定是左右孩子的最小值的下标
            if (elem[child] < elem[parent]) {
                int tmp = elem[parent];
                elem[parent] = elem[child];
                elem[child] = tmp;

                parent = child;
                child = 2 * parent + 1;
            } else {
                break;
            }
        }
    }


    //向上调整建堆的时间复杂度：NlogN
    /**
     * 插入元素，也可以向上调整建堆
     * @param val
     * @return
     */
    public boolean offerHeap(int val) {
        if (isFull()) {
            //扩容
            elem = Arrays.copyOf(elem,elem.length*2);
        }
        elem[usedSize++]=val;
        SshiftUp(usedSize-1);
        return true;
    }

    public boolean isFull() {
        return usedSize==elem.length;
    }


    /**
     * 向上调整算法->小根堆
     * @param child
     * elem 为底层维护的一维数组
     */
    private void SshiftUp(int child) {
        int parent = (child-1)/2;
        while (child >0) {
            if (elem[child]<elem[parent]) {
                int tmp = elem[parent];
                elem[parent] = elem[child];
                elem[child] = tmp;

                child = parent;
                parent = (child-1)/2;
            } else {
                break;
            }
        }
    }

    /**
     * 向上调整算法->大根堆
     * @param child
     * elem 为底层维护的一维数组
     */
    private void BshiftUp(int child) {
        int parent = (child-1)/2;
        while (child >0) {
            // 只需要该这个大于号就行
            if (elem[child]>elem[parent]) {
                int tmp = elem[parent];
                elem[parent] = elem[child];
                elem[child] = tmp;

                child = parent;
                parent = (child-1)/2;
            } else {
                break;
            }
        }
    }




    /**
     * 删除堆顶元素
     */
    public void pollHeap() {
        //判空
        if (isEmpty()) {
            return;
        }
        //交换
        int tmp = elem[usedSize-1];
        elem[usedSize-1] = elem[0];
        elem[0] = tmp;
        //删除+向下调整
        SshiftDown(0,--usedSize);
    }
    public boolean isEmpty() {
        return usedSize == 0;
    }

    public void clear() {
        usedSize = 0;
    }

/*    *//**
     * 前K个时间复杂度NlogK
     * @param arr
     * @param k
     * @return
     *//*
    public int[] maxK(int[] arr, int k) {
        int[] ret = new int[k];
        if(arr == null || k == 0) {
            return ret;
        }

        Queue<Integer> minHeap = new PriorityQueue<>(k);

        //1、遍历数组的前K个 放到堆当中
        for (int i = 0; i < k; i++) {
            minHeap.offer(arr[i]);
        }

        //2、遍历剩下的K-1个，每次和堆顶元素进行比较
        for (int i = k; i < arr.length; i++) {
            if (minHeap.peek()<arr[i]) {
                minHeap.poll();
                minHeap.offer(arr[i]);

            }
        }
        // 堆顶元素 小的时候，就出堆。
        for (int i = 0; i < k; i++) {
            ret[i] = minHeap.poll();
        }
        return ret;
    }

    class IntCmp implements Comparator<Integer> {

        @Override
        public int compare(Integer o1, Integer o2) {
            return o2-o1;
        }
    }
    public int[] smallestK(int[] arr, int k) {
        int[] ret = new int[k];
        if (k==0 ||arr == null) {
            return ret;
        }
        IntCmp intCmp = new IntCmp();
        Queue<Integer> maxheap = new PriorityQueue<>(intCmp);
        for (int i = 0; i < k; i++) {
            maxheap.offer(arr[i]);
        }
        for (int i = k; i < arr.length; i++) {
            if (maxheap.peek()>arr[i]) {
                maxheap.poll();
                maxheap.offer(arr[i]);
            }
        }
        for (int i = 0; i < k; i++) {
            ret[i] = maxheap.poll();
        }
        return ret;
    }*/

}
